This invention relates to a method and apparatus for providing a communication bridge interconnecting two or more local area networks.
Local area networks (LANS) enable local communication among computing stations and computer related devices. As a LAN installation grows, bridges are employed to interconnect LANS so as to allow stations connected to different LANS to communicate as if both stations were on the same LAN. Thus, a bridge is an N port device, where N is equal to or greater than 2. Considerable work has been expended on so-called transparent interconnection of LANS with bridges. For example, the paper "Transparent Interconnection of Local Area Networks with Bridges" (J. Telecomm Networks Vol. 3, pp. 116-130, Summer 1984) discloses a bridge wherein each bridge independently constructs and maintains its own routing database. The routing database contains one entry for each station address the bridge knows together with appropriate routing data. Each entry also contains an age field or time stamp. When the time stamp is too old the entry is deleted, obsolete entries are reduced. Forwarding a data packet (frame) received by a bridge from a LAN requires looking up the destination in the routing data base of the bridge. If the bridge finds the destination address, it employs the routing data to forward the data packet to the indicated address unless that LAN was the source for the data packet. If the destination is not found, the data packet is broadcast on or forwarded to all the LAN connections with the bridge except the one on which it was received. Whenever the forwarding process uses a database entry it resets the particular time stamp.
It is known to employ hashing techniques in such arrangements. A hash table comprises applying an algorithm to data in order to define the table location or position of the hash table into which selected data is written. To retrieve the data, the hash algorithm is applied to the search item. As is known, applying a hash algorithm can produce an event termed "a collision" wherein items hash to the same location in the table, these are called synonyms. In the event of a collision, the synonym is placed elsewhere. This is achieved by secondary probing in which a series of table locations are searched until an empty one is found. Similarly, on retrieval, a process of secondary probing is employed to access the table location in the event that the first location contains an entry for a different address. One known arrangement which employs hashing is described in an article entitled "The Design and Implementation of a Transparent MAN/LAN Gateway", by De Grandi, G.; Garrett, M. W.; Albanese, A.; Lee, T. H. CEC JRC, Ispra, Italy; Editors Fasano, D.; Kennelly, C.; Polishuk, P., EFOC/LAN 86 Proceedings. Papers presented at: The Fourth Annual European Fibre Optical Communications and Local Area Networks Exposition 146-51 1986, 27-27 June 1986, Amsterdam, Netherlands, Publ: Inf. Gatekeepers, Boston, Mass., USA. In this arrangement a data packet has destination and source addresses and is filtered by hashing a 48 bit address field into 14 bits and pointing into table of 16, 384 entries, each of 1 bit. This table contains a "1" for each host belonging to the local population. The table is updated according to the information in the source address field of the packets coming into the bridge from the local LAN. These packets are processed in that the source address is hashed and the results placed in an interprocessor communication port. This port is then read to set the appropriate bite in the 16 kilobit table.
As technology has progressed, it has been possible to increase the speed of the LANS and still employ the aforementioned bridges. As this speed increases, each accessing of the routing data for the processing of each data packet needs to take place within a shorter and shorter predetermined bounded frame time. However, the aforementioned bridges have a time limit within which to process a data packet. For example, it has been found that with bridges employing hash algorithms, when collisions in the hash table occur and secondary probing must be employed, it is difficult to finish the processing of a data packet within the frame time. A possible solution to this problem is to employ content addressable memories. Such memories are discussed in the article "Transparent Interconnections of Broadcast Networks" by W. D. Sincoskie (1986 International Zurich Seminar on Digital Communications). In this document, there is disclosed a drop filter which can insert a source address and look up a destination address in the minimum packet interarrival time. As stated therein, the fastest content addressable memory is one in which each memory cell in the drop filter incorporates an exclusive-OR gate. A scheme is recommended where the entries in the drop set are timed and entries which have not been reinforced by another packet from the host in a certain maximum time T are dropped. Unfortunately, content addressable memories are a specialized item and are complicated. Consequently, they are expensive. Furthermore, estimates need to be made of the number of locations needed in a CAM when a LAN network is being constructed. Thus, there can come a time when it is necessary to delete some addresses in the CAM as it becomes overloaded. Finally, another problem which also applies to the aforementioned bridges, is that although the techniques apply easily to the interconnection of two local area networks, it is difficult to generalize the process parameters to connecting three or more local area networks.